1. Field of the Invention
The present invention relates to a route searching circuit for determining an apparatus to which a packet should be transferred, based on a destination address which specifies a transmission destination of the packet. Also, the present invention relates to a communication apparatus such as a router which uses the route searching circuit.
2. Description of the Related Art
A route searching circuit determines a network address which is defined based on an address such as an IP address on the internet and a mask length.
As an apparatus for relaying a packet data between networks or local area networks (LANs) connected to each other, an apparatus such as a bridge and a router is well known. In an Open Systems Interconnection (OSI) reference model which is defined by the International Organization for Standard (ISO), the bridge performs the connection in a data link layer, especially, a media access sub-layer. The router performs the connection in a network layer which is the upper layer of the data link layer.
A communication control apparatus which is called the bridge or the router needs to determine which apparatus the reception packet received through the network should be next transmitted to, based on a route table data which is previously provided for the communication control apparatus.
In this determination processing, it is generally determined based on the address stored in an address field of a reception packet data that the reception packet data should be transmitted to which apparatus.
The address used in an LAN will be described below simply.
As the address used on the LAN, there are known the address such as a MAC address in an ethernet network and an ATM address in an ATM network which is physically peculiar to the apparatus, a network number of a network to which the apparatus is connected, and a network address indicating a number of the apparatus on the network.
The data transmitted on the LAN generally contains network addresses of a transmission destination and transmission origin in the network layer. As the internet work address, for example, an IP address of 32 bits in the TCP/IP protocol is well known. In the following explanation, the IP address is used.
A router refers to a destination IP address of the received packet to determine that the router should next transmit the packet to which router or terminal. In this determining process, it is first determined which network address the destination IP address of the received packet belongs to. Then, a physical address of the transmission destination corresponding to the network address is determined. The network address is determined based on the IP address and the mask length. The mask length is the data that a predetermined number of bits of the IP address from the most significant bit are significant.
FIG. 1 shows an example of the network address. Referring to FIG. 1, because the mask length is xe2x80x9c16xe2x80x9d, it can be found that the upper 16 bits of the IP address of xe2x80x9c800A0000xe2x80x9d is valid as the network address. When the mask length is xe2x80x9c16xe2x80x9d, the mask address of xe2x80x9cFFFF0000xe2x80x9d that each of the upper 16 bits is xe2x80x9c1xe2x80x9d and each of the lower 16 bits is xe2x80x9c0xe2x80x9d is defined.
When a result of logical product of the above mask address and the destination IP address of the received packet is coincident with the IP address of xe2x80x9c800A0000xe2x80x9d, the destination IP address is coincident with the network address. For example, when the destination IP address is xe2x80x9c800A40C8xe2x80x9d, the logical product of the destination IP address of xe2x80x9c800A40C8xe2x80x9d and the mask data of xe2x80x9cFFFF0000xe2x80x9d is calculated. As a result, the address of xe2x80x9c800A0000xe2x80x9d is obtained. This is coincident with the IP address of xe2x80x9c800A0000xe2x80x9d. Thus, the destination IP address is coincident with the network address.
In a conventional example, the correspondence of the destination IP address and the network address could be simply solved under the concept of xe2x80x9cclassxe2x80x9d. More specifically, when each of the upper bits of the IP address is xe2x80x9c0xe2x80x9d, the IP address belongs to a class A and the mask length is 8 bits. When the upper bit of the IP address is xe2x80x9c10xe2x80x9d, the IP address belongs to a class B and the mask length is 16 bits. When the IP address is xe2x80x9c100xe2x80x9d, the IP address belongs to a class C and the mask length is 24 bits.
At present, the concept of the class is demolished through the spread of subnets and Classless Internet Domain Routing (CIDR). Thus, the network address can not be simply determined from the destination IP address. It takes a long processing time for the determination of the network address. Also, in the network which adopts CIDR, there is a case where one or more network addresses in the route table are coincident with the destination IP address. In this case, the route data of the network address with the longest mask length must be adopted.
However, in a conventional router apparatus of the Internet, the route solution processing for determining based on the destination IP address that a packet should be transmitted to which apparatus is realized by software.
As described above, in a conventional communication control apparatus such as a bridge and a router, there is a problem that it takes a very long processing time for the solution of the route data for packet transfer in the network which has a lot of route data. Especially, in the packet transfer in the network in which there are one or more network addresses matching to an address, the algorithm to solve the network address becomes complicated. Therefore, the determination of the route data takes more time. For these reasons, the throughput of the packet transfer processing decreases in the packet transfer apparatus. This is because a specific route data corresponding to the destination address is searched from a lot of route data by the software.
In addition to the above conventional examples, a routing system is described in Japanese Laid Open Patent Application (JP-A-Heisei 2-206237). In the routing system, a connection apparatus includes an address table for a sub-tree. When a communication frame is received, the address table is referred to. When a destination address is exist in the address table, the communication frame is transferred to a link corresponding to the destination address.
Also, an address comparing system is described in Japanese Laid Open Patent Application (JP-A-Heisei 4-352534). In the address comparing system, an address common section Acom of terminal addresses Al to An set for a plurality of terminal equipments 1-1 to 1-n is stored in an address register 2. A portion of a terminal address of a reception address RA corresponding to the address common section Acom is compared with the value of the address register 2. More specifically, a control register 4 is provided to have mask bits in which presence or non-presence of address comparison is set in units of bits. The address register 2 value and the reception address RA are compared by a comparing section 3 based on the mask bits of the control register 4.
Also, a communication network system is described in Japanese Laid Open Patent Application (JP-A-Heisei 6-62029). In the communication network system, a distribution tree is generated based on tree addresses by a tree leader. A tree address correlation is generated using a network identifier and a node identifier, and a list of connected nodes is generated for every member of the multicast tree set.
Also, a LAN connecting apparatus is described in Japanese Laid Open Patent Application (JP-A-Heisei 7-254912). In the LAN connecting apparatus, an IP header 4 is detected from a reception communication packet 5, and a destination IP address is detected from the IP header 4. An output port number and the destination target IP address corresponding to the IP address are searched from the routing table 11a storing target IP addresses and an output port number for designating a transmission destination LAN for every IP address.
Also, a memory is described in Japanese Laid Open Patent Application (JP-A-Heisei 7-143156). In the memory, an input register for storing an L-bit data and M data base registers for storing X-bit data. The content of the input register is compared with each of the M data base registers in units of bits. When all bits are coincident with each other in one or more of the M registers, a coincidence signal is outputted. A data base mask register is provided for each of the M data base registers to designate whether the comparing operation is to be performed in units of bits.
Also, a route determining apparatus is described in Japanese Laid Open Patent Application (JP-A-Heisei 4-140948). In the route determining apparatus, there is a node address register for storing an address to determine a communication route of a node. Also, an upper mesh register, a gate way address register and a channel bit register are provided. An exclusive OR of the value of the node address register and the destination node address is calculated, and the calculation result is masked with the value of the upper mesh register. When the masked value is not 0, a destination unit is determined from the value of the gate way register. When the masked value is 0, the exclusive OR calculating result is masked with the value of the channel bit register for every communication unit. When the masked data is not 0, a communication request is issued. Then, one is selected from the communication units which issue the transmission requests.
The present invention is accomplished to solve the above problems. Therefore, an object of the present invention is to provide a route searching circuit in which the time required to determine a route can be reduced, so that the load to a CPU can be reduced.
Another object of the present invention is to provide a communication control apparatus using such a route searching circuit.
In order to achieve an aspect of the present invention, a communication control apparatus includes an input and output unit responsive to reception of a packet, for generating a search request and a destination address of the packet to receive a resultant route data, and for transmitting the packet based on the resultant route data. A memory stores a route tree table having a tree structure of a plurality of nodes, each of which has a node data. A route searching circuit refers to the route tree table in response to the search request to determine a route data of a final node data as the resultant route data from the destination address, and outputs the resultant route to the input and output unit.
The route searching circuit includes a next node selecting circuit for referring to the route tree table using the destination address and a predetermined mask data in response to the search request to retrieve a first next node data, for repeatedly referring to the route tree table using an address and mask data of a current node data to retrieve a second next node data, while the first next node data or the second next node data is set as the current node data, until the final node data is obtained.
The route tree table may have a dichotomy tree structure, and each of the plurality of nodes as a parent node is connected to a left child node and a right child node. In this case, the next node selecting circuit selects one of the left child node and the right child node based on a set of the destination address and a predetermined mask data or a set of the address and mask data of the current node data each time the route tree table is referred to.
Also, the next node selecting circuit may select one of the left child node and the right child node based on a (the mask data +1)-th bit of the destination address. In this case, when the next node selecting circuit refers to the route tree table based on a node number, the next node selecting circuit includes a first selector for determining an evaluation bit based on the mask data and the destination address, a second selector for selecting one of a number of the left child node and a number of the right child node based on the evaluation bit, a storing circuit for storing a top node number, and a third selector for selecting one of a top node number and the selected child node number in response to the search request.
Also, the route searching circuit may further include a search end determining circuit for determining whether the final node data is obtained. In this case, the search end determining circuit desirably determines that the final node data is obtained, when there is no node to be referred to or when the second next node data includes an invalidity indicating data.
Also, the route searching circuit may further include a route updating circuit for selectively updating a held route data to a route data of the first or second next node data. In this case, the route updating circuit may update the held route data to the route data of the first or second next node data, when a logical product of the mask data and the destination address is coincident with the address of the first or second next node data. Also, the route updating circuit may include a masking circuit for masking the destination address using the mask data, an address comparing circuit for comparing the masked destination address and the address of the first or second next node data, and a resultant route data updating circuit for updating the held route data to the route data of the first or second next node data, when the masked destination address is coincident with the address of the first or second next node data, and when a validity data of the first or second next node data indicates that the route data of the first or second next node data is valid.
Further, the route searching circuit includes a next mask selecting circuit for selecting one of a right child node mask data and left child node mask data of the route data as a selected child node mask data for a next clock cycle based on an evaluation bit determined based on the destination address and the selected child node mask data for a current clock cycle.
In this case, the route searching circuit may include a next node selecting circuit for referring to the route tree table using the destination address and a predetermined mask data in response to the search request to retrieve a first next node data including the right child node mask data and the left child node mask data, for repeatedly referring to the route tree table using an address of a current node data and the selected child node mask data to retrieve a second next node data including the right child node mask data and the left child node mask data, while the first next node data or the second next node data is set as the current node data, until the final node data is obtained.
The route tree table may has a dichotomy tree structure, and each of the plurality of nodes as a parent node is connected to a left child node and a right child node. Also, the next node selecting circuit selects one of the left child node and the right child node based on a set of the destination address and a predetermined mask data or a set of the address of the current node data and the selected child node mask data each time the route tree table is referred to.
Also, the next node selecting circuit may select one of the left child node and the right child node based on a (the selected child node mask data +1)-th bit of the destination address. In this case, the next node selecting circuit refers to the route tree table based on a node number. The next node selecting circuit may include a first selector for determining an evaluation bit based on the selected child node mask data and the destination address in the current clock cycle, a flip-flop circuit for holding the evaluation bit to output in the next clock cycle, a second selector for selecting one of a number of the left child node and a number of the right child node based on the evaluation bit in the next clock cycle, a storing circuit for storing a top node number, and a third selector for selecting one of the top node number and the selected child node number in the next clock cycle in response to the search request.
Further, the route searching circuit further includes a search end determining circuit for determining whether the final node data is obtained. In this case, the search end determining circuit determines that the final node data is obtained, when there is no node to be referred to or when the second next node data includes an invalidity indicating data.
In addition, the route searching circuit may further include a route updating circuit for selectively updating a held route data to a route data of the first or second next node data. In this case, the route updating circuit updates the held route data to the route data of the first or second next node data, when a logical product of the selected child node mask data and the destination address is coincident with the address of the first or second next node data. Also, the route updating circuit may include a masking circuit for masking the destination address using the mask data in the current clock cycle, a flip-flop for holding the masked destination address to output in the next clock cycle, an address comparing circuit for comparing the masked destination address and the address of the first or second next node data in the next clock cycle, and a resultant route data updating circuit for updating the held route data to the route data of the first or second next node data in the next clock cycle, when the masked destination address is coincident with the address of the first or second next node data, and when a validity data of the first or second next node data indicates that the route data of the first or second next node data is valid.
In order to achieve another aspect of the present invention, a method of determining a route to a destination unit based on a destination address of a packet in a communication control apparatus, includes the steps of:
generating a search request and a destination address of a packet;
referring to a route tree table in response to the search request to determine a route data of a final node data as the resultant route data from the destination address, the route tree table having a tree structure of a plurality of nodes, each of which has a node data; and
transmitting the packet to a destination unit based on the resultant route data.
The referring step may include repeatedly referring to the route tree table using the destination address and a predetermined mask data or using an address and mask data of a current node data to retrieve a second next node data, while the first next node data or the second next node data is set as the current node data, until the final node data is obtained.
In this case, the repeatedly referring step may include selecting one of a right child node mask data and left child node mask data of the route data as a selected child node mask data for a next clock cycle based on an evaluation bit determined based on the destination address and the selected child node mask data for a current clock cycle.